1. Technical Field
This invention generally relates to data processing, and more specifically relates to the sending of digital information between computers such as computers on a network.
2. Background Art
Computer networks have been developed that allow computer systems to communicate with each other. In many computer networks, computers need to transfer large amounts of data over a transmission line. The computer often sends this data using a software program that creates a stack of work to do in memory. The software program then informs the transmission hardware there is data in the stack to be sent via a kickoff indicator set for the hardware. The hardware will then fetch information off this stack and handle sending the data to another computer processor or system across a transmission cable.
When information is passed along a cable, the transmission time can be long and often subject to errors introduced by noise. In many computer systems such as those described above, data is sent in packets and checked to ensure no packets have been dropped due to the noise of the cable. The computer at the receiving end informs the sending computer it has received completed data packets. Hence, for reliably connected systems, acknowledges need to be sent from the receiving system to the sending system and a mechanism in the sending system for handling acknowledges and resending dropped packets is required.
A common method for implementing a packet data transmission system is to have the sending side create, queue and send packets, and then wait for an acknowledge message to be returned before deleting the packets corresponding to the acknowledge message from the queue. If packets are lost due to errors, the sending side will time out, indicated by no acknowledge packet having been received in a defined period of time, and the sender will then resend the packets. Since any lost packets are still in the queue, this is a simple matter of resetting the ‘next packet to send’ pointer back to the packet which timed out and resending the packets from that point in the queue.
In the prior art method, the sending queue needed to internally queue all the pending packets waiting for acknowledgment, including all the packets that are in flight on the transmission media. Increasing the length of the transmission media and hence the delay increases the number of data packets in flight. Also, increasing the transmission frequency increases the number of packets in flight.
In addition, to reduce the amount of bandwidth used to acknowledge packets received, acknowledge messages are often coalesced. In a coalesced system, rather than specifically acknowledging each individual packet, one acknowledge message may acknowledge multiple sent packets. Coalescing increases the difficulty of determining which packet is lost as there is not a one-one correspondence with packets sent to acknowledges received, and increases the number of packets that are held in the sending queue waiting for acknowledgment.
The disadvantage of the prior art approach is that the number of packets that can be in flight is limited by the depth of the queue in the sending interface chip. For small packet sizes and short transmission times the queue size is manageable, but it can be seen that the size can grow substantially for larger packet sizes, increased transmission lengths and higher transmission speeds. Infiniband is an emerging high speed network interconnect technology. In an Infiniband system a 4 k packet is used. The prior art approach would require an increasing number of 4 k packets to achieve longer transmission lengths. For this reason, the required queue size becomes very costly. Thus traditional techniques for queuing packets are not economically feasible for high speed, long transmission line systems that need high reliability and efficient resending of dropped packets.